﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace CSEngine
{
    public enum MinOrMax { MIN, MAX };

    public sealed class MediumAI : AI
    {
        public int DEPTH = 4;

        public MediumAI() { }

        public Move GetNextMove(object sender, PlayerTurnArgs e)
        {
            Minimax minimax = new Minimax(e.Board, e.LastPlayer.Color, DEPTH);

            return minimax.getBestMove();
        }

    }

    public class Minimax
    {
        private const int INF = 9999;
        private const int NEG_INF = -9999;
        private static SpaceColor[,] board = new SpaceColor[15, 15];
        private static byte lowX, lowY, highX, highY;

        Node originNode;

        public Minimax(GameBoard gameBoard, SpaceColor color, int maxDepth)
        {
            init(gameBoard);
            initBoundingBox();

            for(byte x=0; x<15; x++)
                for(byte y=0; y<15; y++)
                    if (board[x, y] == SpaceColor.EMPTY)
                        originNode = new Node(color, maxDepth);
        }

        public void initBoundingBox()
        {
            for (byte x = 0; x < 15; x++)
                for (byte y = 0; y < 15; y++)
                    updateBoundingBox(x, y);
        }

        public static void updateBoundingBox(byte x, byte y)
        {
            if (board[x, y] != SpaceColor.EMPTY)
            {
                if (x <= lowX)
                {
                    lowX = x;
                    if (x != 0)
                        lowX--;
                }
                if (y <= lowY)
                {
                    lowY = y;
                    if (y > 0)
                        lowY--;
                }
                if (x >= highX)
                {
                    highX = x;
                    if (x < 14)
                        highX++;
                }
                if (y >= highY)
                {
                    highY = y;
                    if (y < 14)
                        highY++;
                }


            }
        }

        public static bool legalIndices(int x, int y)
        {
            return (x >= 0 && x < 15 && y >= 0 && y < 15);
        }

        //Convert GameBoard to byte[,] representation
        private void init(GameBoard gameBoard)
        {
            for (int i = 1; i <= 15; i++)
                for (int j = 1; j <= 15; j++)
                    board[i - 1, j - 1] = gameBoard.GetSpace((HexDigit)i, (HexDigit)j).Color;
        }

        public Move getBestMove()
        {
            Console.WriteLine("Starting to evaluate tree");
            originNode.maxtest(NEG_INF, INF);

            Node bestNode = originNode.children[0];
            int topScore  = originNode.children[0].getScore();
            
            foreach (var child in originNode.children)
                if (child.getScore() > topScore)
                {
                    bestNode = child;
                    topScore = bestNode.getScore();
                }

            //Convert back to Move
            return new Move((HexDigit)(bestNode.move.x + 1), (HexDigit)(bestNode.move.y + 1));
        }

        private static MinOrMax opposite(MinOrMax m)
        {
            return (m == MinOrMax.MAX) ? MinOrMax.MIN : MinOrMax.MAX;
        }

        private static SpaceColor opposite(SpaceColor c)
        {
            return (c == SpaceColor.WHITE) ? SpaceColor.BLACK : SpaceColor.WHITE;
        }

        private class MyMove
        {
            public byte x, y;
            public SpaceColor color, prevColor;

            public MyMove(byte x, byte y, SpaceColor color)
            {
                this.x = x;
                this.y = y;
                this.color = color;
            }
            public MyMove(MyMove move)
            {
                this.x = move.x;
                this.y = move.y;
                this.color = move.color;
            }

            public void doMove()
            {
                prevColor = board[x, y];
                board[x, y] = color;

                updateBoundingBox(x, y);
            }

            public void undoMove()
            {
                board[x, y] = prevColor;
            }
        }

        private class Node
        {
            public MyMove move;
            public int score, depth;

            public List<Node> children;

            public Node(SpaceColor firstColor, int maxDepth) // Only used for Origin Node.
            {
                depth = maxDepth;

                for(byte x=0; x<15; x++)
                    for(byte y=0; y<15; y++)
                        if (board[x, y] == SpaceColor.EMPTY)
                        {
                            move = new MyMove(x, y, SpaceColor.EMPTY);
                            x = 15; 
                            y = 15;
                        }

                //createChildren(firstColor);
            }

            public Node(MyMove newMove, int newDepth)
            {
                move = newMove;
                depth = newDepth;
                
                if (depth <= 0)
                    return;
                
                move.doMove();
                //createChildren(opposite(move.color));

                move.undoMove();
            }

            public void createChildren(SpaceColor childColor)
            {
                children = new List<Node>();

                for (byte i = lowX; i <= highX; i++)
                    for (byte j = lowY; j <= highY; j++)
                        if (board[i, j] == SpaceColor.EMPTY && Node.goodSpot(i, j))
                            children.Add(new Node(new MyMove(i, j, childColor), depth - 1));
            }

            public static bool goodSpot(byte x, byte y) //check if there are any close pieces
            {
                int lowXint = (x - 1);
                int lowYint = (y - 1);
                byte lowX = (byte)lowXint;
                byte lowY = (byte)lowYint;
                byte highX = (byte)(x + 1);
                byte highY = (byte)(y + 1);

                if (lowXint < 0) lowX = 0;
                if (lowYint < 0) lowY = 0;
                if (highX > 14) highX = 14;
                if (highY > 14) highY = 14;

                for (byte i = lowX; i <= highX; i++)
                    for (byte j = lowY; j <= highY; j++)
                        if (board[i, j] != SpaceColor.EMPTY)
                            return true;
                //Didn't find any pieces nearby, probably a trash move.
                return false;
            }

            public bool terminatingCondition(SpaceColor color)
            {
                int count = 0;
                for(byte i=0; i<15; i++)
                    for (byte j = 0; j < 15; j++)
                    {
                        if (board[i, j] == color)
                            count++;
                        else
                            count = 0;

                        if (count >= 5)
                            return true;
                    }

                count = 0;
                for (byte i = 0; i < 15; i++)
                    for (byte j = 0; j < 15; j++)
                    {
                        if (board[j, i] == color)
                            count++;
                        else
                            count = 0;

                        if (count >= 5)
                            return true;
                    }

                //Down Diagonals
                for (byte i = 0; i < 11; i++)
                    for (byte j = 0; j < (15-i); j++) // Down diagonals along X axis
                    {
                        if (board[i+j, j] == color)
                            count++;
                        else
                            count = 0;

                        if (count >= 5)
                            return true;
                    }

                for (byte i = 0; i < 11; i++)
                    for (byte j = 0; j < (15 - i); j++) // Down diagonals along Y axis
                    {
                        if (board[j, i + j] == color)
                            count++;
                        else
                            count = 0;

                        if (count >= 5)
                            return true;
                    }

                //Up Diagonals
                for (byte i = 3; i < 14; i++)
                    for (byte j = 0; j <= i; j++) // Up diagonals along X axis
                    {
                        if (board[i - j, j] == color)
                            count++;
                        else
                            count = 0;

                        if (count >= 5)
                            return true;
                    }
                for (byte i = 3; i < 14; i++)
                    for (byte j = 0; j <= i; j++) // Up diagonals along X axis
                    {
                        if (board[j, i - j] == color)
                            count++;
                        else
                            count = 0;

                        if (count >= 5)
                            return true;
                    }

                return false;


                //////Old Style////// 
                /*int count = 0;
                for(byte i=0; i<15; i++)
                    for (byte j = 0; j < 15; j++)
                    {
                        if (board[i, j] != SpaceColor.EMPTY)
                        {
                            for(int k=-4; k<5; k++)
                                if(legalIndices(i+k, j))
                                {
                                    if (board[i + k, j] == color)
                                        count++;
                                    else
                                        count = 0;

                                    if(count >= 5)
                                        return true;
                                }

                            count = 0;
                            for (int k = -4; k < 5; k++)
                                if(legalIndices(i, j+k))
                                {
                                    if (board[i, j + k] == color)
                                        count++;
                                    else
                                        count = 0;

                                    if(count >= 5)
                                        return true;
                                }

                            count = 0;
                            for (int k = -4; k < 5; k++)
                                if(legalIndices(i+k, j+k))
                                {
                                    if (board[i + k, j + k] == color)
                                        count++;
                                    else
                                        count = 0;

                                    if(count >= 5)
                                        return true;
                                }

                            count = 0;
                            for (int k = -4; k < 5; k++)
                                if(legalIndices(i+k, j-k))
                                {
                                    if (board[i + k, j - k] == color)
                                        count++;
                                    else
                                        count = 0;

                                    if(count >= 5)
                                        return true;
                                }

                        }
                    }
                return false;*/
            }

            public void evaluateBoard()
            {
                score = 0;
                SpaceColor myColor = move.color;
                SpaceColor enemyColor = opposite(myColor);

                if (terminatingCondition(myColor))
                {
                    setScore(INF);
                    return;
                }
                if (terminatingCondition(enemyColor))
                {
                    setScore(NEG_INF);
                    return;
                }

                int tempScore = 0;

                for(byte x = 0; x < 15; x++){
                    for (byte y = 0; y < 15; y++)
                    {
                        if(board[x, y] != SpaceColor.EMPTY)
                        {
                            /////// My Score ///////
                            score += scoreChains(move, myColor, 1, 0);  //Horizontal
                            score += scoreChains(move, myColor, 0, 1);  //vertical
                            score += scoreChains(move, myColor, 1, 1);  //UpDiag
                            score += scoreChains(move, myColor, 1, -1); //DownDiag

                            ////// Enemy Score //////
                            score -= scoreChains(move, enemyColor, 1, 0);  //Horizontal
                            score -= scoreChains(move, enemyColor, 0, 1);  //vertical
                            score -= scoreChains(move, enemyColor, 1, 1);  //UpDiag
                            score -= scoreChains(move, enemyColor, 1, -1); //DownDiag
                        }
                    }
                }
                if (score <= NEG_INF)
                    setScore(NEG_INF);
                else if (score >= INF)
                    setScore(INF);
                else
                    setScore(score);
            }

            public void maxtest(int alpha, int beta)
            {
                move.doMove();
                if (depth == 0 || terminatingCondition(SpaceColor.WHITE) || terminatingCondition(SpaceColor.BLACK))
                {
                    evaluateBoard();
                    move.undoMove();
                    return;
                }
                children = new List<Node>();
                for (byte i = lowX; i <= highX; i++)
                    for (byte j = lowY; j <= highY; j++)
                        if (board[i, j] == SpaceColor.EMPTY && Node.goodSpot(i, j))
                        {
                            Node child = new Node(new MyMove(i, j, opposite(move.color)), depth - 1);
                            children.Add(child);

                            child.mintest(alpha, beta);
                            alpha = Math.Max(alpha, child.getScore());

                            if (beta <= alpha)
                                break;

                        }
                score = alpha;
                move.undoMove();
            }

                /*foreach (var child in children)
                {
                    child.mintest(alpha, beta);
                    alpha = Math.Max(alpha, child.getScore());

                    if (beta <= alpha)
                        break;
                }*/

                
            public void mintest(int alpha, int beta)
            {
                move.doMove();
                if (depth == 0 || terminatingCondition(SpaceColor.WHITE) || terminatingCondition(SpaceColor.BLACK))
                {
                    evaluateBoard();
                    move.undoMove();
                    return;
                }

                children = new List<Node>();
                for (byte i = lowX; i <= highX; i++)
                    for (byte j = lowY; j <= highY; j++)
                        if (board[i, j] == SpaceColor.EMPTY && Node.goodSpot(i, j))
                        {
                            Node child = new Node(new MyMove(i, j, opposite(move.color)), depth - 1);
                            children.Add(child);

                            child.maxtest(alpha, beta);
                            beta = Math.Min(beta, child.getScore());

                            if (beta <= alpha)
                                break;
                        }
                score = beta;
                move.undoMove();
            }
                /*
                foreach (var child in children)
                {
                    child.maxtest(alpha, beta);
                    beta = Math.Min(beta, child.getScore());

                    if (beta <= alpha)
                        break;
                }*/

               
            /*
            public void getBestMove(int alpha, int beta)
            {
                if (move.color != SpaceColor.EMPTY)
                    move.doMove();
                if (depth == 0)
                {
                    evaluateBoard();
                    if (move.color != SpaceColor.EMPTY)
                        move.undoMove();
                    return;
                }

                foreach (var child in children)
                {
                    child.getWorstMove(alpha, beta);
                    alpha = Math.Max(alpha, -child.getScore());

                    if (beta <= alpha)
                    {
                        score = alpha;
                        break;
                    }
                    if (beta <= alpha)
                    {
                        score = beta;
                        break;
                    }
                }
                if (move.color != SpaceColor.EMPTY)
                    move.undoMove();
            }

            public void getWorstMove(int alpha, int beta)
            {
                if (move.color != SpaceColor.EMPTY)
                    move.doMove();

                if (depth == 0)
                {
                    evaluateBoard();
                    if (move.color != SpaceColor.EMPTY)
                        move.undoMove();
                    return;
                }

                foreach (var child in children)
                {
                    child.getBestMove(alpha, beta);
                    beta = Math.Min(beta, -child.getScore());

                    if (beta <= alpha)
                    {
                        score = beta;
                        break;
                    }
                    if (beta <= alpha)
                    {
                        score = alpha;
                        break;
                    }
                }

                if (move.color != SpaceColor.EMPTY)
                    move.undoMove();
            }
            */
            int scoreChains(MyMove move, SpaceColor myColor, int incrX, int incrY)
            {
                int count = chainCount(move, myColor, incrX, incrY);
                switch (count)
                {
                    case 0: return 0;
                    case 1: return 1;
                    case 2: return 3;
                    case 3: return 12;
                    default: return INF;
                }
            }

            int chainCount(MyMove move, SpaceColor myColor, int incrX, int incrY)
            {
                byte x = move.x;
                byte y = move.y;

                int count = 0;

                //first direction (EX: Left)
                while (true)
                {
                    x = (byte)(x + incrX);
                    y = (byte)(y + incrY);

                    if (!legalIndices(x, y) || board[x, y] != myColor)
                        break;

                    count++;
                }

                //opposite direction (EX: Right)
                x = move.x;
                y = move.y;
                while (true)
                {
                    x = (byte)(x - incrX);
                    y = (byte)(y - incrY);

                    if (!legalIndices(x, y) || board[x, y] != myColor)
                        break;

                    count++;
                }
                return count;
            }

            public void setScore(int newScore)
            {
                double depthFactor = (4 + depth);
                depthFactor /= 8;
                score = (int)(newScore * depthFactor);
            }

            public int getScore()
            {
                return score;
            }
        }
    }
}
